 #include <stdio.h>
 #include <stdlib.h>

// 求a [1,2,3,4], b [1,2,3]两个序列的卷积


void arr_moveright(int arr[], int n) {
	int idx = n - 1;
	while (idx > 0) {
		arr[idx] = arr[idx-1];
		idx--;
	}
	arr[0] = 0;
}


// 方法1、翻转相乘，比较直观

//   [0 0 1 2 3 4]
// x [3 2 1 0 0 0]
// 相乘相加结果为1

// b向右平移，继续相乘相加
//   [0 0 1 2 3 4]
// x [0 3 2 1 0 0]
// 结果为4
void convolution1(int a[], int b[], int L1, int L2, int **res, int *L) {
	int len = L1 + L2 - 1;

	int *x = calloc(len, sizeof(int));
	int *h = calloc(len, sizeof(int));
	for (int i = 0; i < L1; i++) x[len-1 - i] = a[L1-1 - i];
	for (int i = 0; i < L2; i++) h[i] = b[L2-1 - i];

	*res = malloc(sizeof(int) * len);
	for (int i = 0; i < len; i++) {
		int sum = 0;
		for (int j = 0; j < len; j++) 
			sum += x[j]*h[j];

		printf("%d ", sum);
		(*res)[i] = x[i]*h[i];		
		arr_moveright(h, len);
	}
	*L = len;
	free(x); free(h);
}

// 方法2、时延法，更简单
// 过程：
// x[n]*y[0]并平移到位置0	→ 图像1
// x[n]*y[1]并平移到位置1	→ 图像2
// ...
// 所有图像叠加，即得到x[n]*y[n]
void convolution2(int a[], int b[], int L1, int L2, int **res, int *L) {
	int len = L1 + L2 - 1;
	*res = calloc(len, sizeof(int));
	for (int i = 0; i < L1; i++) {
		for (int j = 0; j < L2; j++) {
			(*res)[i + j] += a[i] * b[j];
		}
	}
	for (int i = 0; i < len; i++)
		printf("%d ", (*res)[i]);
	*L = len;
}

int main()
{
	int a[] = {1,2,3,4};
	int b[] = {1,2,3};
	int L1 = sizeof(a) / sizeof(a[0]);
	int L2 = sizeof(b) / sizeof(b[0]);
	

	int *res, len;
	convolution2(a, b, L1, L2, &res, &len);
	// for (int i = 0; i < len; i++)
	// 	printf("%d ", res[i]);

	return 0;
}